#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 056. 合并区间.py
@time: 2022/1/13 16:51
@desc: https://leetcode-cn.com/problems/merge-intervals/
> 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

@解题思路：
    1. 强者思路，我不配，倒是学会了lambda的拼写
    2. Ot(NlogN), Os(logN)
'''

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        # 按start排序
        intervals.sort(key= lambda x: x[0])

        merge = []
        for interval in intervals:
            # 当列表为空或者目前区间的start大于列表的最大end，则没有重合，直接加入
            if not merge or merge[-1][1]<interval[0]:
                merge.append(interval)
            # 否则需要更新原来的最大end
            else:
                merge[-1][1] = max(interval[1], merge[-1][1])
        return merge